package com.tree;

import com.tree.lang.Node;

/**
 * @name: BinaryTree
 * @author: 李昂
 * @date: 2021-04-15 19:54
 * @description：BinaryTree
 * @update: 2021-04-15 19:54
 */
public class BinaryTree<key extends Comparable<key>, value> {

    //存储根节点
    private Node root;
    //记录树的节点个数
    private int size;

    //树的节点个数
    public int getSize() {
        return size;
    }

    public void put(key k, value v) {
        root = put(root, k, v);
    }

    //向树中添加节点个数
    public Node put(Node x, key k, value v) {
        if (x == null) {
            size++;
            return new Node(k, v, null, null);
        }

        int cmp = k.compareTo((key) x.k);
        if (cmp > 0) {
            x.right = put(x.right, k, v);
        } else if (cmp < 0) {
            x.left = put(x.left, k, v);
        } else {
            x.v = v;
        }

        return x;
    }

    //获取二叉树中的值
    public value get(key k) {
        return get(root, k);
    }


    public value get(Node x, key k) {

        if (x == null) {
            return null;
        }

        int cmp = k.compareTo((key) x.k);
        if (cmp > 0) {
            return get(x.right, k);
        } else if (cmp < 0) {
            return get(x.left, k);
        } else {
            return (value) x.v;
        }

    }

    public void delete(key k) {
        root = delete(root, k);
    }


    public Node delete(Node x, key k) {

        if (x == null) {
            return null;
        }

        int cmp = k.compareTo((key) x.k);

        if (cmp > 0) {
            x.right = delete(x.right, k);
        } else if (cmp < 0) {
            x.left = delete(x.left, k);
        } else {

            if (x.right == null) {
                size--;
                return x.left;
            }
            if (x.left == null) {
                size--;
                return x.right;
            }

            Node minNode = x.right;
            while (minNode.left != null) {
                if (minNode.left.left == null) {
                    break;
                }
                minNode = minNode.left;
            }

            Node n = minNode.left.right;

            minNode.left.left = x.left;

            minNode.left.right = x.right;

            x = minNode.left;

            minNode.left= n;

            size--;

        }

        return x;
    }

    public static void main(String[] args) {

        BinaryTree<Integer, String> bt = new BinaryTree<>();
        bt.put(8, "李昂");
        bt.put(3, "张三");
        bt.put(7, "李四");
        bt.put(4, "王五");
        bt.put(6, "赵六");
        bt.put(2, "刘能");
        bt.put(9, "王嘛");
        bt.put(5, "赵四");


        System.out.println("长度---》" + bt.getSize());


        bt.delete(4);

        System.out.println(bt.get(2));
        System.out.println(bt.get(6));
        System.out.println(bt.get(4));
        System.out.println(bt.get(7));
        System.out.println(bt.get(8));
        System.out.println(bt.get(3));
        System.out.println(bt.get(9));
        System.out.println(bt.get(5));

        System.out.println("长度---》" + bt.getSize());

    }


}
